原文題目
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

題目摘要

1. 目標是找到所有組合，使得這些數字的和等於 target。
2. 同一數字可以被多次選擇使用。
3. 每個組合皆是唯一的。

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

解題思路

1. 設定串列：
   • 建立一個二維串列 result 來存儲所有符合條件的組合。
   • 建立一個串列 combination 用來儲存當前正在嘗試的組合。
2. 遞迴尋找組合：
   • 定義遞迴函數 findCombination，參數包含候選數組 candidates、目標 target、當前處理的索引 index、當前組合 combination、當前總和 total 和結果數組 result。
3. 達到目標值的情況：
   • 如果當前總和 total 等於目標值 target，表示找到一個符合條件的組合，將當前組合複製並加入到 result 中，然後返回。
4. 超過目標值或遍歷完候選數字的情況：
   • 如果當前總和 total 超過目標值 target 或者索引 index 已超過候選數字的範圍，表示當前路徑不可行，直接返回。
5. 選擇當前候選數字：
   • 將候選數字 candidates[index] 加入到當前組合中，並將其值加入到 total 中。
   • 遞迴處理當前索引，繼續嘗試使用相同的候選數字來達到目標值，即調用 findCombination(candidates, target, index, combination, total + candidates[index], result)。
6. 撤銷選擇並嘗試下一個候選數字：
   • 完成上述遞迴後，從 combination 中移除已加入的候選數字，來撤銷剛才的選擇。
   • 將索引移至下一個候選數字，並遞調用 findCombination(candidates, target, index + 1, combination, total, result)進行遞迴處理。
7. 遞迴終止條件：
   • 當符合條件的組合被找到或所有可能的組合都已經被嘗試時，遞迴結束。
8. 回傳結果：
   • 遞迴完成後， 將回傳包含所有符合條件組合的result。

程式碼

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>(); //設立結果的二維串列用來存儲所有符合條件的組合
        List<Integer> combination = new ArrayList<>(); //設立串列用來儲存尋找符合條件組合時的當前組合

        findCombination(candidates, target, 0, combination, 0, result);
        return result;        
    }

    //用來尋找符合條件組合的遞迴方法
    private void findCombination(int[] candidates, int target, int idex, List<Integer> combination, int total, List<List<Integer>> result) {
        // 如果當前總和等於目標值，將當前組合加入結果列表中
        if (total == target) {
            result.add(new ArrayList<>(combination));
            return;
        }

        // 如果當前總和超過目標值或已經遍歷所有候選數字，則返回
        if (total > target || idex >= candidates.length) {
            return;
        }

        // 選擇當前候選數字並進行下一步遞迴
        combination.add(candidates[idex]);
        findCombination(candidates, target, idex, combination, total + candidates[idex], result);

        // 撤回選擇，移除當前候選數字，並遞迴檢查下一個候選數字
        combination.remove(combination.size() - 1);
        findCombination(candidates, target, idex + 1, combination, total, result);
    }    
}

結論
認識回溯法後，就會知道如何遞迴和設立終止條件是關鍵的步驟，只要能規劃好如何遞迴及設立適當的終止條件，就能快速解出這題。這題的解法主要是利用遞迴來逐步嘗試不同數字的組合，直到總和等於目標值。在每一步中，我們可以選擇當前的數字並進行進一步的遞迴，直到總和超過或達到目標值。如果超過了目標值，則進行回溯，結束這條路徑的遞迴並回到上一步選擇。如果找到一組符合條件的組合，就將其加入到結果列表中。最後，遞迴遍歷所有可能的組合並回傳結果。